package lc169;

/**
 * @Author Stringzhua
 * @Date 2024/3/25 18:24
 * description:pro169
 */
public class MajorityElement {
    //第一种解法:士兵胜利法
//        public int majorityElement(int[] nums) {
//            if (nums == null || nums.length == 0) return Integer.MIN_VALUE;
//            int winner = nums[0];
//            int count = 1;
//            for (int i = 0; i < nums.length; i++) {
//                if (nums[i] == winner) count++;
//                else if (count == 0) {
//                    winner =  nums[i];
//                    count++;
//                }else {
//                    count--;
//                }
//            }
//            return winner;
//        }
    public int majorityElement(int[] nums) {
        //第二种解法:摩尔投票法
        return candudate(nums, 0);
    }

    private int candudate(int[] nums, int index) {
        int i = index;
        int c = nums[index];
        int count = 1;
        while (i < nums.length - 1 && count > 0) {
            i += 1;
            if (nums[i] == c) {
                count++;
            } else {
                count--;
            }
        }
        //判断是否遍历得到是中位数的数组的值
        if (i == nums.length - 1) {
            return c;
        } else {
            return candudate(nums, i + 1);
        }
    }
//定义摩尔投票方法

    public static void main(String[] args) {
        MajorityElement majorityElement = new MajorityElement();
        System.out.println(majorityElement.majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2, 2,}));
    }
}
